# ---
# title: 787. Cheapest Flights Within K Stops
# id: problem787
# author: Indigo
# date: 2021-01-28
# difficulty: Medium
# categories: Dynamic Programming, Heap, Breadth-first Search
# link: <https://leetcode.com/problems/cheapest-flights-within-k-stops/description/>
# hidden: true
# ---
# 
# There are `n` cities connected by `m` flights. Each flight starts from city
# `u` and arrives at `v` with a price `w`.
# 
# Now given all the cities and flights, together with starting city `src` and
# the destination `dst`, your task is to find the cheapest price from `src` to
# `dst` with up to `k` stops. If there is no such route, output `-1`.
# 
#     
#     
#     **Example 1:**
#     Input: 
#     n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
#     src = 0, dst = 2, k = 1
#     Output: 200
#     Explanation: 
#     The graph looks like this:
#     ![](https://s3-lc-upload.s3.amazonaws.com/uploads/2018/02/16/995.png)
#     
#     The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
#     
#     
#     **Example 2:**
#     Input: 
#     n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
#     src = 0, dst = 2, k = 0
#     Output: 500
#     Explanation: 
#     The graph looks like this:
#     ![](https://s3-lc-upload.s3.amazonaws.com/uploads/2018/02/16/995.png)
#     
#     The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.
#     
# 
# 
# 
# **Constraints:**
# 
#   * The number of nodes `n` will be in range `[1, 100]`, with nodes labeled from `0` to `n`` - 1`.
#   * The size of `flights` will be in range `[0, n * (n - 1) / 2]`.
#   * The format of each flight will be `(src, ``dst``, price)`.
#   * The price of each flight will be in the range `[1, 10000]`.
#   * `k` is in the range of `[0, n - 1]`.
#   * There will not be any duplicated flights or self cycles.
# 
# 
## @lc code=start
using LeetCode

function find_cheapest_price(n::Int, flights::Vector{Vector{Int}}, src::Int, dst::Int, K::Int)
    graph = [Dict{Int, Int}() for i in 1:n]
    for flight in flights
        graph[flight[1]][flight[2]] = flight[3]
    end
    cost = fill(typemax(Int) >> 1, n)
    cost[src] = 0
    changed = [src]
    for i in 1:K+1
        tmp = Int[]
        for new_s in changed
            for (s_to_t, st_cost) in graph[new_s]
                if cost[s_to_t] > st_cost + cost[new_s]
                    cost[s_to_t] = st_cost + cost[new_s]
                    push!(tmp, s_to_t)
                end
            end
        end
        changed = tmp
    end
    return (cost[dst] == typemax(Int) >> 1) ? -1 : cost[dst]
end
## @lc code=end
